package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/01/09 22:58
 **/
public class Day1_9_Review {
    class Solution25 {
        // 方法一：
        public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                }else {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            if(l1 == null) cur.next = l2;
            if(l2 == null) cur.next = l1;
            return dummyHead.next;
        }

        // 方法二：递归
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }

    class Solution26 {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(A == null || B == null) return false;
            return isSubStructureHelp(A, B) || isSubStructure(A.left, B) ||isSubStructure(A.right, B);
        }
        public boolean isSubStructureHelp(TreeNode A, TreeNode B) {
            if(B == null) return true;
            if(A == null) return false;
            return A.val == B.val && isSubStructureHelp(A.left, B.left) && isSubStructureHelp(A.right, B.right);
        }
    }

    class Solution27 {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) return root;
            TreeNode l = root.left;
            TreeNode r = root.right;
            root.left = r;
            root.right = l;
            mirrorTree(root.left);
            mirrorTree(root.right);
            return root;
        }
    }

    class Solution68_Ⅱ {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return null;
            if(root.val == p.val) return p;
            if(root.val == q.val) return q;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if(l != null && r != null) return root;
            if(l != null) return l;
            return r;
        }
    }

    class Solution68_Ⅰ {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return root;
            if(root.val < p.val && root.val < q.val) {
                return lowestCommonAncestor(root.right, p, q);
            }else if(root.val > p.val && root.val > q.val) {
                return lowestCommonAncestor(root.left, p, q);
            }else {
                return root;
            }
        }
    }
}